package ch4.part2;

import java.util.Arrays;

/**
 * 鸡尾酒排序，双向冒泡排序
 * 平均时间复杂度：O(n)=n^2
 * 大多数元素已是有序时，时间复杂度最优，为O(n)=n
 *
 * @author liuwanxiang
 * @version 2019/05/17
 */
public class CocktailSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 4, 5, 6, 7, 8, 1};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void sort(int[] array) {
        int tempData;
        boolean isSorted;
        for (int i = 0; i < array.length / 2; i++) {
            isSorted = true;
            for (int j = i; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    tempData = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tempData;
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }

            isSorted = true;
            for (int j = array.length - i - 1; j > i; j--) {
                if (array[j - 1] > array[j]) {
                    tempData = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tempData;
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }


}
